home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8383 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.4 KB

  1. Path: garden.csc.calpoly.edu!not-for-mail
  2. From: dstubbs@garden.csc.calpoly.edu (Dan Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Sorting algorithm - In search of
  5. Date: 3 Mar 1996 14:06:31 -0800
  6. Organization: Cal Poly, San Luis Obispo
  7. Message-ID: <4hd557$ai2@garden.csc.calpoly.edu>
  8. References: <4h4jmq$3bh@news.cis.nctu.edu.tw> <4h6glr$ab6@utrhcs.cs.utwente.nl> <4hat5g$bdq@fohnix.metronet.com>
  9. NNTP-Posting-User: dstubbs@garden.csc.calpoly.edu
  10.  
  11. In article <4hat5g$bdq@fohnix.metronet.com>,
  12. Stan Milam <milam@fohnix.metronet.com> wrote:
  13. >Frans F.J. Faase (faase@cs.utwente.nl) wrote:
  14. >: In article <4h4jmq$3bh@news.cis.nctu.edu.tw>, Don Pierce <don@pierce.geometrics.com> writes:
  15. >: |> I am looking for an efficient sorting alogorithm
  16. >: |> to sort an array of floats. I prefer a non-recursive
  17. >: |> type because I heard they were inefficient on large data
  18. >: |> sets. My array contains upt 10000 elements
  19. >
  20. >What in the world is wrong with the standard qsort() function.  My experience
  21. >with it is that it is very fast.  Moreover, it is not restricted to a single
  22. >data type.
  23. >
  24. The comment about avoiding recursive sort implementations is not one
  25. that I follow. A common way to implement quicksort is to apply recursion
  26. to long subintervals and to apply non-recursive insertion sort to short
  27. (nearly sorted) subintervals. Such a combination is hard to beat. You should
  28. seek some solid evidence before avoiding a good implementation of (recursive)
  29. quicksort.
  30.  
  31. I agree with the comment about qsort. I many cases it is the sort technique
  32. of choice. However, there may be cases in which qsort is not the best. The
  33. question here concerns sorting an array of floats. It is probably possible
  34. to implement quicksort specifically for an array of floats so that it is
  35. faster than the (generic) qsort. If sorting the array of floats is frequent
  36. and time consuming it is no doubt worth comparing qsort with good 
  37. implementations that are hard wired for the specific problem at hand. 
  38.  
  39. Further, some implementations of qsort do not perform well for certain
  40. initial distributions of the data to sort. If you have such a case, then
  41. you need to replace qsort with another implementation of quicksort that
  42. is efficient for your initial distribution.
  43.  
  44. For the occasional sort application, by all means, use qsort. For production
  45. sort problems test qsort to make sure it provides the performance you need.
  46. If it doesn't investigate an implementation of quicksort that is customized
  47. to your sorting problem.
  48.  
  49.  
  50.  
  51.